Important Data Structure

• array & string
• linked Lists
• stack & queue
• tree & graph

Important algorithms & concepts

• bit manipulations
• probabilities
• OOP
• Recursive & Dynamic Programming
• Sort & Search
• Scalability & memory issues
• Testing

Knowledge

• C++
• database
• thread & lock

Data Structure terms

Tree

Tree = acyclic graph

Binary tree = tree that consists of 2-children nodes

Binary Search Tree = binary tree with the relationship between all parent(p) and left child(l), right child(r), such that l.val <= p.val < r.val

Depth

Min : logn // Max : n

Search

Best : O(logn) // Wost : O(n)

Traverse

pre-order : parent -> left subtree -> right subtree

in-order : left subtree -> parent -> right subtree

post-order : left subtree -> right subtree -> parent

Balanced BST

Red-Black Tree

AVL Tree

Treap : tree + heap, randomized binary search tree

implementation

node implementation

Array vs Dynamic memory

Useful Links

Tree Data structure

Binary Tree

BST